      1  import java.util.Arrays;

      2

      3  /**

      4     A partial solution to the eight queens puzzle.

      5  */

      6  public class PartialSolution

      7  {

      8     private Queen[] queens;

      9     private static final int NQUEENS = 8;

     10

     11     public static final int ACCEPT = 1;

     12     public static final int ABANDON = 2;

     13     public static final int CONTINUE = 3;

     14

     15     /**

     16        Constructs a partial solution of a given size.

     17        @param size the size

     18     */

     19     public PartialSolution(int size)

     20     {

     21        queens = new Queen[size];

     22     }

     23

     24     /**

     25        Examines a partial solution.

     26        @return one of ACCEPT, ABANDON, CONTINUE

     27     */

     28     public int examine()

     29     {

     30        for (int i = 0; i < queens.length; i++)

     31        {

     32           for (int j = i + 1; j < queens.length; j++)

     33           {

     34              if (queens[i].attacks(queens[j])) { return ABANDON; }

     35           }

     36        }

     37        if (queens.length == NQUEENS) { return ACCEPT; }

     38        else { return CONTINUE; }

     39     }

     40

     41     /**

     42        Yields all extensions of this partial solution.

     43        @return an array of partial solutions that extend this solution.

     44     */

     45     public PartialSolution[] extend()

     46     {

     47        // Generate a new solution for each column

     48        PartialSolution[] result = new PartialSolution[NQUEENS];

     49        for (int i = 0; i < result.length; i++)

     50        {

     51           int size = queens.length;

     52

     53           // The new solution has one more row than this one

     54           result[i] = new PartialSolution(size + 1);

     55

     56           // Copy this solution into the new one

     57           for (int j = 0; j < size; j++)

     58           {

     59              result[i].queens[j] = queens[j];

     60           }

     61

     62           // Append the new queen into the ith column

     63           result[i].queens[size] = new Queen(size, i);

     64        }

     65        return result;

     66     }

     67

     68     public String toString() { return Arrays.toString(queens); }

     69  }

     70